1. Field of the Invention
The present invention relates to a Viterbi decoding apparatus and a Viterbi decoding method, and more particularly, is preferably applied to decode encoded data convolutionally encoded by using a Viterbi decoding algorithm in a cellular radio communication system.
2. Description of the Related Art
The field of mobile communication has been quickly advanced in recent years. Particularly, a cellular radio communication system represented by a portable-telephone system has been remarkably developed. In the cellular radio communication system, an area in which communication service is provided is divided into cells of a desired size, a base station serving as a fixed station is set in each of the cells, and a communication terminal unit serving as a mobile station performs radio communication with the base station which is likely under the best available communication condition.
Various systems have been proposed as communication systems of the above cellular radio communication system: for example, the frequency division multiple access (FDMA) system, the time division multiple access (TDMA) system, and the code division multiple access (CDMA) system. Particularly, the CDMA system has an advantage that a lot of channels per cell, that is, a large system capacity can be secured compared to other systems and is noticed as a next-generation cellular radio communication system. Actually, the CDMA system is standardized as the IS-95 standard by the Electronic Industries Association/the Telecommunications Industry Association (EIA/TIA).
Thus, various communication systems have been proposed. However, even when using any communication system, errors may occur in transmission data on a radio transmission line in the case of the cellular radio communication system because the system performs communication through a radio line. Therefore, in the cellular radio communication system, transmission data is convolutionally encoded in order to correct errors in the transmission mode and the encoded data thus obtained is transmitted through a radio transmission line, and the reception side correctly restores the transmitted data by Viterbi-decoding the received encoded data.
The convolutional encoding and Viterbi-decoding are specifically described below. The convolutional encoding is generally referred to as error correction coding, which is an encoding system for dispersing the information of transmission data into a plurality of data by successively applying the convolutional operation to the transmission data to be input. An encoder used for the convolutional encoding is constituted, for example, as shown in FIG. 1. That is, a convolutional encoder 1 is constituted with a shift register 2 having a proper number of stages for successively capturing and shifting input transmission data S1 and exclusive OR circuits 3 and 4 for performing a convolutional operation by applying the exclusive OR operation to the register value at a predetermined stage of the shift register 2. The convolutional encoder 1 is a circuit for outputting output values C1 and C2 of the exclusive OR circuits 3 and 4 as encoded data.
Normally, in the case of convolutional encoding, the number of stages of a shift register is referred to as a constraint length and the rate of the number of encoded data to be output for an input of one bit is referred to as an encoding rate, and the convolutional encoding characteristic is specified by these parameters. In FIG. 1, the number of stages of the shift register 2 is xe2x80x9c3xe2x80x9d and the encoded data of two bits is output for the input of one bit. Therefore, as for the convolutional encoding characteristic, the constraint length is xe2x80x9c3xe2x80x9d and the encoding rate is xe2x80x9cxc2xdxe2x80x9d.
The encoded data to be output in the convolutional encoding is determined in accordance with a value currently stored in a shift register and a value currently input, and has regularity. For example, in FIG. 1, encoded data values (c1 and c2) are determined in accordance with the two-bit values (a2 and a3) being currently in the shift register 2 and the one-bit value (a1) currently input. In this case, when assuming that four states determined by the two bits (a2 and a3 ) being in the shift register 2 are referred to as xe2x80x9cAxe2x80x9d, xe2x80x9cBxe2x80x9d, xe2x80x9cCxe2x80x9d, and xe2x80x9cDxe2x80x9d, the convolutional encoding can be expressed by the state transition diagram shown in FIG. 2. In this case, the values written on the arrow for the state transition from each state to the next state denote the encoded data (c1 and c2) to be output and the data (a1) then input.
A trellis diagram is obtained by arranging state-transition arrows output from the states A, B, C, and D shown by the above state transition diagram, in the temporally transverse direction as shown in FIG. 3. In FIG. 3, a continuous line shows the case of an input value xe2x80x9c0xe2x80x9d and a dotted line shows the case of an input value xe2x80x9c1xe2x80x9d. In this connection, each arrow connecting the states is normally referred to as a branch, and a branch route until reaching an optional state is referred to as a path.
In this case, Viterbi decoding restores the convolutionally encoded data to the original data. The Viterbi decoding is also referred to a maximum-likelihood decoding method which restores the correct data to which error correction is applied by observing a received data series while considering a trellis diagram and obtaining the nearest data string on the trellis diagram. An index of likelihood referred to a metric is one of the scales for obtaining the nearest data string. The metric normally uses a hamming distance.
The hamming distance shows the distance between data and generally shows the difference between a received data series and the branch data on a trellis diagram. For example, when the received data series is (1,0), the series is different from the branch (0,0) on the trellis diagram by one bit. Therefore, the hamming distance between these data becomes xe2x80x9c1xe2x80x9d and therefore, the metric for the branch (0,0) results in xe2x80x9c1xe2x80x9d. Moreover, when the received data series is (1,1), it is different from the branch (0,0) on the trellis diagram by two bits. Therefore, the hamming distance between these data becomes xe2x80x9c2xe2x80x9d and the metric for the branch (0,0) results in xe2x80x9c2xe2x80x9d.
The Viterbi decoding computes a data series closest to a received data series by obtaining the metric of a branch (hereafter referred to a branch metric) at each time based on the received data series, obtaining the metrics of two paths (hereafter referred to as path metrics) input to each state based on the branch metric to select a higher-likelihood path, selecting the maximum-likelihood path out of the finally surviving paths, and inversely tracing the maximum-likelihood path (this operation is hereafter referred to as tracing-back).
Here, a case of transmitting a transmission data series (1,0,1,0,1,0,0) is considered as an example. When the above transmission data series is input to the register 2 of the convolutional encoder 1 shown in FIG. 1 under the state in which the register 2 is initially set to (0,0,0), (11,01,00,01,00,01,11) is obtained as the encoded data values c1 and c2. It is assumed that an actually-received reception data series is (01,00,00,01,00,01,11) because an error occurs in a transmission line when such encoded data is transmitted through the radio line.
In the case of Viterbi decoding, as shown in FIG. 4, initial values of path metrics of the states are first uniformly set to xe2x80x9c0xe2x80x9d, the hamming distance between the data value of the received reception data series and the data value of each branch is calculated under the above state to obtain each branch metric, and a path metric is computed in accordance with the branch metric and the path metric at the last time to select a likelihood path at any time. Note that each numeral entered in a circle in FIG. 3 denotes a path metric. For example, at the time t1, two branches from the states A and C are input to the state A. The data value of the branch from the state A is (0,0) and the reception data series is (0,1). Therefore, the branch metric of the branch results in xe2x80x9c1xe2x80x9d. Moreover, since the data value of the branch from the state C is (1,1), the branch metric of the branch also results in xe2x80x9c1xe2x80x9d. In this case, since both the branch metrics are xe2x80x9c1xe2x80x9d, path selection is not performed but the value xe2x80x9c1xe2x80x9d obtained by merely adding the branch metric xe2x80x9c1xe2x80x9d to the path metric xe2x80x9c0xe2x80x9d is set as the path metric of the next state A.
Similarly, at the time t1, two branches from the states A and C are input to the state B. Since the data value of the branch from the state A is (1,1) and the reception data series is (0,1), the branch metric of the branch results in xe2x80x9c1xe2x80x9d. Moreover, since the data value of the branch from the state C is (0,0), the branch metric of the branch also results in xe2x80x9c1xe2x80x9d. Similarly, in this case, since both the branch metrics are xe2x80x9c1xe2x80x9d, path selection is not performed but the value xe2x80x9c1xe2x80x9d obtained by merely adding the branch metric xe2x80x9c1xe2x80x9d to the path metric xe2x80x9c0xe2x80x9d is set as the path metric of the next state B.
Similarly, at the time t1, two branches from the states B and D are input to the state C. Since the data value of the branch from the state B is (0,1) and the reception data series is (0,1), the branch metric of the branch results in xe2x80x9c0xe2x80x9d. Moreover, since the data value of the branch from the state D is (1,0), the branch metric of the branch results in xe2x80x9c2xe2x80x9d. Therefore, in this case, the value xe2x80x9c0xe2x80x9d obtained by selecting the path from the state B (that is, the path from the state D is disused) and adding the branch metric xe2x80x9c0xe2x80x9d to the path metric xe2x80x9c0xe2x80x9d of the state B is set as the path metric of the next state C.
Similarly, at the time t1, two branches from the states B and D are input to the state D. Since the data value of the branch from the state B is (1,0) and the reception data series is (0,1), the branch metric of the branch results in xe2x80x9c2xe2x80x9d. Moreover, since the data value of the branch from the state D is (0,1), the branch metric of the branch results in xe2x80x9c0xe2x80x9d. Therefore, in this case, the value xe2x80x9c0xe2x80x9d obtained by selecting the path from the state D (that is, the path from the state B is disused) and adding the branch metric xe2x80x9c0xe2x80x9d to the path metric xe2x80x9c0xe2x80x9d of the state D is set as the path metric of the next state D.
Hereafter similarly, by computing a path metric based on the received reception data at each of times t2 to t7 and selecting a path, it is possible to form the trellis diagram shown in FIG. 4.
As shown in FIG. 4, at the time t7, xe2x80x9c1xe2x80x9d, xe2x80x9c3xe2x80x9d, xe2x80x9c3xe2x80x9d and xe2x80x9c3xe2x80x9d are finally obtained as the path metrics of the states A, B, C, and D. In this case, since a state having the smallest path metric becomes the maximum-likelihood state, the state A becomes the maximum-likelihood state. Therefore, by performing tracing-back starting with the state A, the correct decoded data (1,0,1,0,1,0,0) is restored with the paths shown by a thick line.
Among the above-described Viterbi algorithms, the path selection by the computation of a path metric and the path-metric computation by the addition of branch metrics are normally referred to as an add compare select (ACS) operation which is realized by an exclusive ACS operation circuit. Moreover, the trellis diagram shown in FIG. 4 is formed by writing the path metric and the surviving paths in a memory referred to as a path memory whenever computing a path metric through the ACS operation.
In the case of a cellular radio communication system, transmission data is normally transmitted every predetermined data unit referred to as a frame. Therefore, the convolutional encoding is performed every frame so that. the convolutional encoding is completed within the frame. When decoding convolutionally encoded data by using the above-described Viterbi algorithms so that the decoding is completed within the frame, the memory length of the path memory serves as an important factor. This is because the Viterbi decoding has a feature that the decoding accuracy can be further improved as the distance for tracing-back is long, that is, as the memory length of the path memory is long. Actually, however, it prevents a receiver from being minimized to use a path memory with a memory length longer than the data length of the encoded data. Therefore, a path memory is normally used that has a length five to six times longer than the constraint length of convolutional encoding.
Thus, in the case of a Viterbi decoder for Viterbi-decoding encoded data by using a path memory having a memory length shorter than the data length of the encoded data, as shown in FIG. 5, when path information which is constituted with a path metric and selected path are fully accumulated in the path memory by normally performing the ACS operation for the memory length of the path memory, first transmission data D1 is decoded by performing tracing-back up to the length of the path memory with the maximum-likelihood state among the final states stored in the path memory as a start point. When the transmission data D1 can be decoded, the first-input path information is disused similarly to a first-in first-out (FIFO) memory. Then, the ACS operation is performed once, the path information obtained through the operation is input to the path memory, and tracing-back is performed up to the path memory length by using the maximum-likelihood state among final states as a start point to decode second transmission data D2. Hereafter, the same processing is repeated so as to decode the transmission data by performing the tracing-back for the path memory length whenever new path information is input to the path memory. After the reception data runs out the, transmission data is decoded by assuming that the reception data xe2x80x9c00xe2x80x9d is received, and by computing path information and similarly performing the tracing-back up to the path memory length.
Thus, a conventional Viterbi decoder secures a necessary decoding accuracy by performing the ACS operation, every time until the final transmission data Dn can be decoded and by performing the tracing-back up to the memory length of the path memory when the memory length of the path memory is shorter than the data length of the encoded data. However, the conventional Viterbi decoder has problems that processing becomes complex because it is necessary to perform the ACS operation every time and to perform tracing-back up to the memory length of the path memory and, thereby, the time required for processing increases, and it is impossible to decode reception data at a high speed.
In view of the foregoing, an object of this invention is to provide a Viterbi decoding apparatus and a Viterbi decoding method capable of improving the decoding accuracy and increasing the decoding speed compared to the case of a conventional apparatus and method.
The foregoing object and other objects of the invention have been achieved by the provision of a Viterbi decoding apparatus and a Viterbi decoding method in which: a tail bit constituted with a predetermined value of (kxe2x88x921) bits is added to the tail of a predetermined-length data string and assuming the constraint length of a convolutional encoder as xe2x80x9ckxe2x80x9d, the initial value of each register of the shift register of the convolutional encoder is set to a predetermined value and the data string to which the tail bit is added is convolutionally encoded with the convolutional encoder so that the symbol string is generated; when the symbol string is received and the data string is decoded from the symbol string, a path metric value weighted based on the initial value of each of the registers is set as the initial path metric value of each state, the path metric value of each state is successively computed on the basis of the initial path metric value whenever the symbol string is received so that surviving paths are stored in a path memory, the data string is decoded one bit by one bit whenever tracing-back is performed for the path memory length with a maximum-likelihood state determined based on the path metric value as a start-point state until the path metric operation reaches the number of data strings, and the data string is decoded one bit by one bit whenever tracing-back is performed for one step by using a fixed state determined based on the value of a tail bit as a start-point state when the path metric operation reaches the final operation for the symbol string.
Thus, the initial path metric value of each state is set to a value weighted based on the initial value of a convolutional encoder, and a data string is decoded one bit by one bit whenever tracing-back is performed for one step by using a fixed state determined by the value of a tail bit as a start-point state when the path metric operation reaches the final operation, thereby a path metric can be computed accurately and the tracing-back frequency can be reduced.
The nature, principle and utility of the invention will become more apparent from the following detailed description when read in conjunction with the accompanying drawings in which like parts are designated by like reference numerals or characters.